// 2025/4/2
// https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
// 最长回文子串

class Solution {
    public:
        string longestPalindrome(string s) {
            int n = s.size(), maxLen = 0; 
            string ans;
            vector<vector<bool>> dp(n, vector<bool>(n, true));
            for(int i = n - 1; i >= 0; i--)
            {
                for(int j = i; j < n; j++)
                {
                    if(s[i] != s[j]) dp[i][j] = false;
                    else if(i != j) dp[i][j] = dp[i + 1][j - 1];
    
                    int len = j - i + 1;
                    if(dp[i][j] && len > maxLen)
                    {
                        maxLen = len;
                        ans = s.substr(i, len);
                    }
                }
            }
            return ans;
        }
    };